package com.c2b.algorithm.leetcode.jzoffer.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * <a href="https://www.nowcoder.com/practice/7fe2212963db4790b57431d9ed259701?tpId=13&tqId=23280&ru=%2Fpractice%2Fa9d0ecbacef9410ca97463e4a5c83be7&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=">从上往下打印二叉树</a>
 * 不分行从上往下打印出二叉树的每个节点，同层节点从左至右打印。例如输入{8,6,10,#,#,2,1}，如以下图中的示例二叉树，则依次打印8,6,10,2,1(空节点不打印，跳过)，请你将打印的结果存放到一个数组里面，返回。
 * <pre>
 *          8
 *         /  \
 *        6    10
 *            /  \
 *           2    1
 *  输入：{8,6,10,#,#,2,1}
 *  返回值：[8,6,10,2,1]
 * </pre>
 *
 * @author c2b
 * @since 2023/3/9 13:44
 */
public class JzOffer0032PrintFromTopToBottom {

    /**
     * <p>队列</p>
     * step 1：首先判断二叉树是否为空，空树没有遍历结果。<br>
     * step 2：建立辅助队列，根节点首先进入队列。不管层次怎么访问，根节点一定是第一个，那它肯定排在队伍的最前面。<br>
     * step 3：每次遍历队首节点，如果它们有子节点，依次(先左后右)加入队列排队等待访问。<br>
     */
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode currNode = queue.poll();
            res.add(currNode.val);
            if (currNode.left != null) {
                queue.offer(currNode.left);
            }
            if (currNode.right != null) {
                queue.offer(currNode.right);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(8);
        root.left = new TreeNode(6);
        root.right = new TreeNode(10);
        root.right.left = new TreeNode(2);
        root.right.right = new TreeNode(1);
        JzOffer0032PrintFromTopToBottom jzOffer0032PrintFromTopToBottom = new JzOffer0032PrintFromTopToBottom();
        ArrayList<Integer> integers = jzOffer0032PrintFromTopToBottom.PrintFromTopToBottom(root);
        for (Integer integer : integers) {
            System.out.println(integer);
        }
    }
}
